JZ23 二叉搜索树的后续遍历序列

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

这题还是挺难的

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

输入：

[4,8,6,12,16,14,10]

返回值

true

解析：一颗二叉搜索树（就是二叉查找树），如下所示

后序遍历为：

[5,7,6,9,11,10,8]

由后序遍历，已经右数一定比 Root 大的特性，只需遍历这个数组，找到第一个比 8 大的下标，将其分成左右子树，按照这种方式，不断的递归。

如果遍历的过程中，先出现了大于根节点的节点，后面又出现了小于根节点的节点，则说明不是二叉搜索树的后序遍历序列。比如 [7,4,6,5] 这样的序列。

class Solution {
    // 要点：二叉搜索树中根节点的值大于左子树中的任何一个节点的值，小于右子树中任何一个节点的值，子树也是
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length < 2) return true;
        return verify(postorder, 0, postorder.length - 1); 
    }

    // 递归实现
    private boolean verify(int[] postorder, int left, int right){
        if (left >= right) return true; // 当前区域不合法的时候直接返回true就好

        int rootValue = postorder[right]; // 当前树的根节点的值

        int k = left;
        // 从当前区域找到第一个大于根节点的，说明后续区域数值都在右子树中
        // 分成两块区域 [5,7,6,9,11,10,8] => [5,7,6] 和 [9,11,10]
        while (k < right && postorder[k] < rootValue){ 
            k++;
        }
        // 进行判断后续的区域是否所有的值都是大于当前的根节点，如果出现小于的值就直接返回false
        for (int i = k; i < right; i++){ 
            if (postorder[i] < rootValue) return false;
        }

        // 当前树没问题就检查左右子树
        if (!verify(postorder, left, k - 1)) return false; // 检查左子树
        if (!verify(postorder, k, right - 1)) return false; // 检查右子树

        return true; // 最终都没问题就返回true
    }
}